package com.wc.alorithm.tree;

import java.util.Scanner;

/**
 * @Author congege
 * @Description 线段树
 * @Date Created in 2023/12/5-22:34
 */
public class SegTree {
    static class Node {
        int l;
        int r;
        // 蓝标记
        int lazy;
        // 区间最大值
        int max;
        // 区间最小值
        int min;
        // 区间和
        int sum;
    }

    static int N;
    static Node[] tree;
    static int[] array;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        tree = new Node[N * 4];
        array = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            array[i] = sc.nextInt();
        }
        build(1, 1, N);
    }

    // 向下传递懒标记
    static void pushDown(int k) {
        if (tree[k].lazy != 0) {
            int lc = k << 1;
            int rc = lc + 1;
            // 给左右孩子上懒
            tree[lc].lazy += tree[k].lazy;
            tree[rc].lazy += tree[k].lazy;
            int mid = (tree[k].l + tree[k].r) >> 1;
            tree[lc].sum += tree[k].lazy * (mid - tree[lc].l + 1);
            tree[rc].sum += tree[k].lazy * (tree[rc].r - mid);
            // 懒标记消除
            tree[k].lazy = 0;
        }
    }

    static void build(int k, int l, int r) {
        tree[k].l = l;
        tree[k].r = r;
        if (l == r) {
            tree[k].max = array[l];
            tree[k].min = array[l];
            tree[k].sum = array[l];
            return;
        }
        int lc = 2 * k;
        int rc = lc + 1;
        int mid = (l + r) / 2;
        build(lc, l, mid);
        build(rc, mid + 1, r);
        tree[k].min = Math.min(tree[lc].min, tree[rc].min);
        tree[k].max = Math.max(tree[lc].max, tree[rc].max);
        tree[k].sum = tree[lc].sum + tree[rc].sum;
    }

    // 最大值最小值一样
    // 区间最大值区间覆盖法
    public static int queryMax1(int k, int l, int r) {
        if (tree[k].l >= l && tree[k].r <= r) {
            return tree[k].max;
        }
        int lc = 2 * k;
        int rc = lc + 1;
        int mid = (tree[k].l + tree[k].r) / 2;
        int maxAns = Integer.MIN_VALUE;
        if (mid >= l) {
            maxAns = Math.max(queryMax1(lc, l, r), maxAns);
        }
        if (mid < r) {
            maxAns = Math.max(queryMax1(rc, l, r), maxAns);
        }
        return maxAns;
    }

    // 区间最大值 区间等值法
    public static int queryMax2(int k, int l, int r) {
        if (tree[k].l == l && tree[k].r == r) {
            return tree[k].max;
        }
        int lc = 2 * k;
        int rc = lc + 1;
        int mid = (tree[k].l + tree[k].r) / 2;
        if (mid >= r) {
            return queryMax2(lc, l, r);
        }
        if (mid <= l) {
            return queryMax2(rc, l, r);
        }
        return Math.max(queryMax2(lc, l, mid), queryMax2(rc, mid + 1, r));
    }

    // 区间求和
    public static int querySum(int k, int l, int r) {
        if (tree[k].l >= l && tree[k].r <= r) {
            return tree[k].sum;
        }
        if (tree[k].r < l || tree[k].l > r) {
            return 0;
        }
        pushDown(k);
        int lc = 2 * k;
        int rc = lc + 1;
        int mid = (tree[k].l + tree[k].r) / 2;
        int sum = 0;
        if (mid >= l) {
            sum += querySum(lc, l, r);
        }
        if (mid + 1 <= r) {
            sum += querySum(rc, l, r);
        }
        return sum;
    }

    // 单点更新，将i位置改为val
    public static void update(int k, int i, int val) {
        if (tree[k].l == tree[k].r && tree[k].l == i) {
            tree[k].sum += val;
            tree[k].max = val;
            tree[k].min = val;
            return;
        }
        // 看这个区间有没有i
        if (tree[k].l > i || tree[k].r < i) {
            return;
        }
        int mid = (tree[k].l + tree[k].r) >> 1;
        int lc = 2 * k;
        int rc = lc + 1;
        if (i <= mid) {
            update(lc, i, val);
        } else {
            update(rc, i, val);
        }

        tree[k].min = Math.min(tree[lc].min, tree[rc].min);
        tree[k].min = Math.max(tree[lc].max, tree[rc].min);
        tree[k].sum = tree[lc].sum + tree[rc].sum;
    }

    // 区间更新 在区间[l,r]都加上val，覆盖式
    public static void updateSection(int k, int l, int r, int val) {
        if (tree[k].l >= l && tree[k].r <= r) {
            tree[k].sum += val * (tree[k].r - tree[k].l + 1);
            tree[k].lazy += val;
            return;
        }
        pushDown(k);
        int lc = k << 1;
        int rc = lc + 1;
        int mid = (tree[k].l + tree[k].r) >> 1;
        if (mid >= l) {
            updateSection(lc, l, r, val);
        }
        if (mid + 1 <= r) {
            updateSection(rc, l, r, val);
        }
        tree[k].sum += tree[lc].sum + tree[rc].sum;
    }
}
